//==============================================================================
//	 GraphTable.cc
//
//==============================================================================
//.......1.........2.........3.........4.........5.........6.........7.........8
//

#include "GraphTable.hh"

//------------------------------------------------------
// * PrintShortestPath
//------------------------------------------------------
// 
void 
GraphTable::PrintShortestPath(ostream &fout,int Start,int End)
{
  PrintShortestPath(fout,Start,End,mPredecessorMatrix);
  cout<<endl;
}

//------------------------------------------------------
// * PrintShortestPath
//------------------------------------------------------
//
void 
GraphTable::PrintShortestPath(ostream &fout,int i,int j,
													 Table<int> &PD)
{
  if (i == j){
	 fout<<i<<"\t";
  }else{
	 if (PD[i][j] == -1){
		fout<<"No path."<<endl;
	 }else{
		PrintShortestPath(fout,i,PD[i][j],PD);
		fout<<j <<"\t";
	 }
  }
}

//------------------------------------------------------
// * ComputeAllPairsShortestPath
//------------------------------------------------------
// Uses Floyd-Warshall algorithm.  
//
void
GraphTable::ComputeAllPairsShortestPath()
{
  this->Copy(mWeightMatrix);
  
  // Ensure that all self links are 0
  
  // Setup predecessor matrix (to recover paths later)
  mPredecessorMatrix.Allocate(mRows,mCols);
  for(int i = 0;i< mRows;i++){
	 for(int j = 0;j<mCols;j++){
		if ((i == j) || (mWeightMatrix[i][j] == MAX_EDGE_WEIGHT)){
		  mPredecessorMatrix[i][j]=-1;// NIL
		}else{
		  mPredecessorMatrix[i][j] = i;
		}
	 }
  }
  // cout<<"Initial p matrix: "<<mPredecessorMatrix.mRows;
  //cout<<mPredecessorMatrix.mCols<<endl;
  //mPredecessorMatrix.Print();

  FloydWarshall(mWeightMatrix,mPredecessorMatrix);

}

//------------------------------------------------------
// * FloydWarshall
//------------------------------------------------------
// An O(n^3) algorithm for all pairs shortest path.   
//
void
GraphTable::FloydWarshall(Table<float> &D,Table<int> &PD)
{
  for(int k = 0;k<D.mRows;k++){
	 for(int i = 0;i<D.mRows;i++){
		for(int j = 0;j<D.mRows;j++){
		  if (D[i][j] > (D[i][k]+D[k][j])){
			 PD[i][j] = PD[k][j];
		  }
		  float MinValue = min(D[i][j],D[i][k]+D[k][j]);
		  D[i][j] = MinValue;
		}
	 }
  }
}

//------------------------------------------------------
// * GetShortestPathNodes
//------------------------------------------------------
//
void
GraphTable::GetShortestPathNodes(int &Start,int &End)
{
  float Min = MAX_EDGE_WEIGHT;
  Start = 0,End = 0;
  for(int r = 0;r<mWeightMatrix.mRows;r++){
	 for(int c = 0;c<mWeightMatrix.mCols;c++){
		if (r != c){
		  if (mWeightMatrix[r][c] < Min){
			 Min = mWeightMatrix[r][c];
			 Start = r;
			 End = c;
		  }
		}
	 }
  }
}

